package com.julius.design.suanfa.dynamic;

/**
 * @author julius
 * @date 2021-10-29 上午 11:36
 * <p>
 *      连续子数组的最大和
 *      输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *      要求时间复杂度为O(n)。
 *
 *      https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
 * </p>
 */
public class MaxSubArray {


    /**
     * nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 连续子数组的最大和: 这里连续子数组的意思就是必须包含最后一个数组
     * 动态规划解法：
     *         状态定义：
     *              动态数组为dp,dp[i]指以nums[i]结尾的最大子数组的和，因为要求是连续子数组，所以必须包含nums[i]
     *              dp[i-1]标识以nums[i-1]结尾的最大子数组的和
     *         转移方程：
     *              如果dp[i-1] <=0，则dp[i] = nums[i],否者dp[i] = dp[i-1]+nums[i]
     *         初始状态：
     *              当i==0,dp[i] = nums[i]
     *         返回值：
     *              返回dp[i]中的最大值
     *
     *         优化：
     *              一般都是优化dp列表
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums){
        //穷举所有可能性
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1;i< nums.length;i++){
            dp[i] = nums[i]+Math.max(dp[i-1],0);
        }
        //找到dp数组中的最大值
        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if(dp[i] >= max){
                max = dp[i];
            }
        }
        return max;
    }


    /**
     * 优化dp数组
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums){
        int maxSubNum = nums[0];
        for (int i = 1;i<nums.length;i++){
            //覆盖当前位置的值
            nums[i] = nums[i]+Math.max(nums[i-1],0);
            //存储最大的连续和
            maxSubNum = Math.max(nums[i],maxSubNum);
        }
        return maxSubNum;
    }

    public static void main(String[] args) {
       int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }


}
